#!/usr/env python
#-*-coding: utf-8 -*-

#MERGE-SORT(A)
# if p < r
#  q = floor((p + r) / 2)
#  MERGE-SORT(A, p, q)
#  MERGE-SORT(A, q+1, r)
#  MERGE(A, p, q, r)
#


class MergeSort:
    
    def __init__(self):
        """classe para objectos com algoritmo merge-sort
        """
        pass
    pass
    
    #
    # MergeSort algoritm
    # - arrayA, the list of object to sort
    # - pValue, the initial list position
    # - rValue, the last position
    def merge_Sort(self, arrayA, pValue, rValue):
        """ Merge-Sort algoritm to  sort a list
        of unsorted objects.
        arrayA - the list of object to sort
        pValue - the initial list position
        rValue - the last position
        """
        if pValue < rValue:
            #q = math.floor((pValue + rValue) / 2)
            
            qVal = (pValue + rValue) / 2
            #qVal = math.floor(qVal)
            self.merge_Sort(arrayA, pValue, qVal)
            self.merge_Sort(arrayA, qVal+1, rValue)
            
            self.__merge(arrayA, pValue, qVal, rValue)
        pass
    pass
    
    #merge function used on mergesort algoritm to order the list
    def __merge(self, arrayA, pVal, qVal, rVal):
        n1_val = qVal - pVal + 1
        n2_val = rVal - qVal
        
        left_list = [arrayA[pVal +i] for i in range(0, n1_val)]
##        left_list.append(99999)
        left_list.append('zzzzz')
        right_list = [arrayA[qVal +j +1] for j in range(0, n2_val)]
##        right_list.append(99999)
        right_list.append('zzzzz')
        
        i = 0
        j = 0
        for k in range(pVal, rVal):
            if left_list[i] <= right_list[j]:
                arrayA[k] = left_list[i]
                i +=1
            else:
                arrayA[k] = right_list[j]
                j +=1
            pass
        pass
    pass
pass
